class Solution {
public:
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    int partitionArray(vector<int> &nums, int k) {
        // write your code here
        int len = nums.size();
        if( len == 0 )
            return 0;

        int start = 0, end = len - 1;
        int tmp = 0;
        while( start < end ){
            while( start < end && nums[start] < k)
                start++;
            while(start < end && nums[end] >= k)
                end--;
            if(start < end){
                tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
                start++;
                end--;
            }
        }
        
        if(nums[start] >= k)
            return start;
        return start+1;
    }
};
